#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 13
#define P 13
#define OK 1
#define ERROR 0
#define DUPLICATE -1
#define TRUE 1
#define FALSE 0

typedef struct {
	int key;
	int flag;
} ElemType;

typedef struct {
	ElemType data[MAXSIZE];
	int count;
} HashTable;

int d1[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14}; /* 线性探测序列 */
int d2[15] = {0, 1, -1, 2, -2, 3, -3, 4, -4, 5, -5, 6, -6, 7, -7}; /* 二次探测序列 */

void dataset(int ds[], int *len);
int InsertHash(HashTable *H, int e, int d[]);
int CreateHash(HashTable *H, int ds[], int len, int d[]);
int SearchHash(HashTable *H, int e, int d[]);
void menu();

/* 输入查找表 */
void dataset(int ds[], int *len) {
	int n, m;
	n = 0;
	printf("\n查找表输入：");
	while (scanf("%d", &m) == 1) { /* 以输入一个非整数作为结束 */
		ds[n] = m;
		n++;
	}
	*len = n;
}

/* 计算哈希地址，插入哈希表 */
int InsertHash(HashTable *H, int e, int d[]) {
	int k = e % P;
	int i = 1;
	while (H->data[k].flag == TRUE && H->data[k].key != e) {
		k = (e % P + d[i]) % MAXSIZE;
		i++;
		if (i >= 15) {
			return ERROR;
		}
	}
	if (H->data[k].flag == TRUE) {
		return DUPLICATE;
	}
	H->data[k].key = e;
	H->data[k].flag = TRUE;
	H->count++;
	return OK;
}

/* 构造哈希表 */
int CreateHash(HashTable *H, int ds[], int len, int d[]) {
	int i;
	for (i = 0; i < len; i++) {
		if (SearchHash(H, ds[i], d) != -1) {
			return DUPLICATE;
		}
		if (InsertHash(H, ds[i], d) == ERROR) {
			return ERROR;
		}
	}
	return OK;
}

/* 初始化哈希表 */
void InitHash(HashTable *H) {
	int i;
	for (i = 0; i < MAXSIZE; i++) {
		H->data[i].key = 0;
		H->data[i].flag = FALSE;
	}
	H->count = 0;
}

/* 在哈希表中查找 */
int SearchHash(HashTable *H, int e, int d[]) {
	int k = e % P;
	int i = 1;
	while (H->data[k].flag && H->data[k].key != e) {
		k = (e % P + d[i]) % MAXSIZE;
		i++;
		if (i >= 15) {
			return -1;
		}
	}
	if (H->data[k].flag) {
		return k;
	} else {
		return -1;
	}
}

/* 演示菜单 */
void menu() {
	int choice;
	int *p;
	HashTable h;
	InitHash(&h); /* 初始化哈希表 */
	printf("\n----哈希查找演示----\n");
	printf("\n1.线性探测构造哈希表\n");
	printf("\n2.二次探测构造哈希表\n");
	printf("\n3.退出\n");
	printf("\n输入选择：");
	scanf("%d", &choice);
	if (choice == 1) {
		p = d1;
	} else if (choice == 2) {
		p = d2;
	} else {
		return;
	}
	int a[MAXSIZE];
	int len;
	dataset(a, &len); /* 建立查找表 */
	if (CreateHash(&h, a, len, p) == ERROR) {
		printf("\n哈希表构造失败！\n");
	} else if (CreateHash(&h, a, len, p) == DUPLICATE) {
		printf("\n哈希表具有重复关键字！\n");
	} else {
		printf("\n哈希表：\n");
		for (int i = 0; i < MAXSIZE; i++) {
			printf("%3d", h.data[i].key);
		}
		printf("\n\n哈希查找\n输入要查找的key值：");
		int e;
		scanf("%d", &e);
		int index = SearchHash(&h, e, p);
		if (index != -1) {
			printf("\n%d在哈希表中下标为%d\n", e, index);
		} else {
			printf("\n%d未找到\n", e);
		}
	}
}

int main() {
	menu();
	return 0;
}

